package com.foxzzz.binary.search;

public class Solution441 {

    //(mid + 1) >(n-1-mid)*2/mid
    public int arrangeCoins(int n) {
        int low = 0;
        int high = n;
        while (low <= high) {
            int mid = (int) ((long) (low + high) / 2);

            //n*2/mid>=mid
            if (mid <= ((long)n * 2 / (mid * 1.0) - 1) && (mid + 1) >(n-1-mid)/(mid*1.0)*2)
                return mid;
            else if (mid < ((long)n * 2 / (mid * 1.0) - 1)) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return 0;
    }

    public static void main(String[] args) {
        System.out.println(new Solution441().arrangeCoins(5));
        System.out.println(new Solution441().arrangeCoins(8));
        System.out.println(new Solution441().arrangeCoins(1804289383));
    }
}
